#define  _CRT_SECURE_NO_WARNINGS
// class Solution {
//     int m;
//     int n;
//     int dx[4] = {0,0,1,-1};
//     int dy[4] = {1,-1,0,0};
// public:
//     void solve(vector<vector<char>>& board) {
//         m = board.size();
//         n = board[0].size();
//         vector<vector<bool>> visit(m, vector<bool>(n, false));
//         for(int i = 0; i < m; i++)
//         {
//             if(board[i][0] == 'O' && !visit[i][0]) bfs1(board, i, 0, visit);
//             if(board[i][n - 1] == 'O' && !visit[i][n - 1]) bfs1(board, i, n - 1, visit);
//         }
//         for(int i = 0; i < n; i++)
//         {
//             if(board[0][i] == 'O' && !visit[0][i]) bfs1(board, 0, i, visit);
//             if(board[m - 1][i] == 'O' && !visit[m - 1][i]) bfs1(board, m - 1, i, visit);
//         }
//         for(int i = 0; i < m; i++)
//         {
//             for(int j = 0; j < n; j++)
//             {
//                 if(board[i][j] == 'O' && visit[i][j] == false)
//                     bfs2(board, i, j, visit);
//             }
//         }
//     }
//     void bfs1(vector<vector<char>>& board, int sr, int sc, vector<vector<bool>>& visit)
//     {
//         queue<pair<int, int>> q;
//         q.push({sr, sc});
//         visit[sr][sc] = true;
//         while(q.size())
//         {
//             auto [r, c] = q.front(); q.pop();
//             for(int i = 0; i < 4; i++)
//             {
//                 int x = r + dx[i];
//                 int y = c + dy[i];
//                 if(x >= 0 && x < m && y >= 0 && y < n
//                 && board[x][y] == 'O' && !visit[x][y])
//                     q.push({x, y}), visit[x][y] = true;
//             }
//         }
//     }
//     void bfs2(vector<vector<char>>& board, int sr, int sc, vector<vector<bool>>& visit)
//     {
//         queue<pair<int, int>> q;
//         q.push({sr, sc});
//         visit[sr][sc] = true;
//         board[sr][sc] = 'X';
//         while(q.size())
//         {
//             auto [r, c] = q.front(); q.pop();
//             for(int i = 0; i < 4; i++)
//             {
//                 int x = r + dx[i];
//                 int y = c + dy[i];
//                 if(x >= 0 && x < m && y >= 0 && y < n
//                 && board[x][y] == 'O' && !visit[x][y])
//                     q.push({x, y}), visit[x][y] = true, board[x][y] = 'X';
//             }
//         }
//     }
// };
class Solution {
    int m;
    int n;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
public:
    void solve(vector<vector<char>>& board) {
        m = board.size();
        n = board[0].size();
        for (int i = 0; i < m; i++)
        {
            if (board[i][0] == 'O') bfs(board, i, 0);
            if (board[i][n - 1] == 'O') bfs(board, i, n - 1);
        }
        for (int i = 0; i < n; i++)
        {
            if (board[0][i] == 'O') bfs(board, 0, i);
            if (board[m - 1][i] == 'O') bfs(board, m - 1, i);
        }
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '6') board[i][j] = 'O';
            }
        }
    }
    void bfs(vector<vector<char>>& board, int sr, int sc)
    {
        queue<pair<int, int>> q;
        q.push({ sr, sc });
        board[sr][sc] = '6';
        while (q.size())
        {
            auto [r, c] = q.front(); q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = r + dx[i];
                int y = c + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n
                    && board[x][y] == 'O')
                    q.push({ x, y }), board[x][y] = '6';
            }
        }
    }
};